#include <iostream>
#include <cmath>

using namespace std;

#include "tporo.h"
#include "tlistaporo.h"
#include "tpilaporo.h"
#include "tvectorporo.h"
#include "tcolaabbporo.h"

#include "tabbporo.h"


// Constructor por defecto
TNodoABB::TNodoABB()
{
   this->iz=NULL;
   this->de=NULL;
}
// Constructor de copia
TNodoABB::TNodoABB (const TNodoABB &original)
{
   this->item=original.item;
   this->iz = new TABBPoro (*original.iz);
   this->de = new TABBPoro (*original.de);
}
// Destructor
TNodoABB::~TNodoABB()
{
   if(this->iz != NULL)delete this->iz;
   if(this->de != NULL)delete this->de;
   this->iz=NULL;
   this->de=NULL;
}
// Sobrecarga del operador asignación
TNodoABB& TNodoABB::operator=(const TNodoABB &original)
{
   if(this!=&original)
   {
      this->item=original.item;
      this->iz = new TABBPoro (*original.iz);
      this->de = new TABBPoro (*original.de);
   }
   return *this;
}


// Constructor por defecto
TABBPoro::TABBPoro()
{
   this->nodo=NULL;
}
// Constructor de copia
TABBPoro::TABBPoro(const TABBPoro &arbol)
{
    /*
   if(original.nodo != NULL)this->nodo = new TNodoABB(*original.nodo);
   if(original.nodo->iz!=NULL)this->nodo->iz=new TABBPoro(*original.nodo->iz);
   if(original.nodo->de!=NULL)this->nodo->de=new TABBPoro(*original.nodo->de);
   */
   nodo = NULL;

    if(arbol.nodo != NULL)
    {
        Insertar(arbol.nodo->item);
        if(arbol.nodo->iz != NULL)nodo->iz = new TABBPoro(*arbol.nodo->iz);
        if(arbol.nodo->de != NULL)nodo->de = new TABBPoro(* arbol.nodo->de);
    }
    else
        nodo = NULL;
}
// Destructor
TABBPoro::~TABBPoro()
{
   if(this->nodo!=NULL)
   {
      delete this->nodo;
      this->nodo=NULL;
   }
}
// Sobrecarga del operador asignación
TABBPoro& TABBPoro::operator=(const TABBPoro &original)
{
   if(this!=&original)
   {
      if(this->nodo!=NULL)
      {
         while(this->EsVacio() != true)
         {
            this->Borrar(this->nodo->item);
         }
         delete this->nodo;
      }
      if(original.nodo)
      {
         Insertar(original.nodo->item);
         if(original.nodo->iz!=NULL)this->nodo->iz=new TABBPoro(*original.nodo->iz);
         if(original.nodo->de!=NULL)this->nodo->de=new TABBPoro(*original.nodo->de);
      }
   }
   return *this;
}
// Sobrecarga del operador igualdad
bool TABBPoro::operator==(const TABBPoro &otro)const
{/*
   if(nodo->item!=otro.nodo->item)
   {
      return false;
   }
   else
   {
      bool de=true;
      bool iz=true;
      if(otro.nodo->iz!=NULL && !(*this->nodo->iz==*otro.nodo->iz))iz=false;
      if(otro.nodo->de!=NULL && !(*this->nodo->de==*otro.nodo->de))de=false;
      if(otro.nodo->iz==NULL && this->nodo->iz!=NULL)iz=false;
      if(otro.nodo->de==NULL && this->nodo->de!=NULL)de=false;
      return (iz && de);
   }*/
   TVectorPoro niveles,inorden,postorden,preorden;
   TVectorPoro niveles2,inorden2,postorden2,preorden2;
   //~ niveles=this->Niveles();
   inorden=this->Inorden();
   postorden=this->Postorden();
   preorden=this->Preorden();
   //~ niveles2=otro.Niveles();
   inorden2=otro.Inorden();
   postorden2=otro.Postorden();
   preorden2=otro.Preorden();
   return (inorden==inorden2 || preorden==preorden2 || postorden==postorden2);
}
// Devuelve TRUE si el árbol está vacío, FALSE en caso contrario
bool TABBPoro::EsVacio()const
{
   if(this->nodo==NULL)
      return true;
   else
      return false;
}
// Inserta el elemento en el árbol
bool TABBPoro::Insertar(const TPoro &poro)
{
   if(this==NULL)return false;
   else if(this->nodo==NULL)
   {
      this->nodo=new TNodoABB();
      this->nodo->item=poro;
      return true;
   }
   else
      if(this->nodo->item.Volumen()==poro.Volumen())
         return false;//NO HACE NADA
      else
         if(this->nodo->item.Volumen()>poro.Volumen())
            if(this->nodo->iz)
               return this->nodo->iz->Insertar(poro);
            else
            {
               this->nodo->iz=new TABBPoro();
               return this->nodo->iz->Insertar(poro);
            }
         else
            if(this->nodo->de)
               return this->nodo->de->Insertar(poro);
            else
            {
               this->nodo->de=new TABBPoro();
               return this->nodo->de->Insertar(poro);
            }
}
// Borra el elemento en el árbol
bool TABBPoro::Borrar(const TPoro &poro)
{
   if(this==NULL || this->nodo == NULL || EsVacio() || !Buscar(poro))
   {
      return false;
   }
   else
   {
      bool borrado=false;
      double nVolumen=this->nodo->item.Volumen();
      double pVolumen=poro.Volumen();
      TABBPoro* iz=this->nodo->iz;
      TABBPoro* de=this->nodo->de;

      if(nVolumen > pVolumen)
      {
         if(iz)borrado = iz->Borrar(poro);
         if(iz->nodo==NULL)
         {
            delete iz;
            this->nodo->iz=NULL;
         }
      }
      else if(nVolumen < pVolumen)
      {
         if(de)borrado = de->Borrar(poro);
         if(de->nodo==NULL)
         {
            delete de;
            this->nodo->de=NULL;
         }
      }
      else if ( nVolumen==pVolumen && iz == NULL && de == NULL)
      {
         delete this->nodo;
         this->nodo=NULL;
         borrado=true;
      }
      else if (nVolumen == pVolumen && de == NULL)
      {
         this->nodo->item=iz->nodo->item;
         this->nodo->iz=iz->nodo->iz;
         this->nodo->de=iz->nodo->de;
         iz->nodo->iz=iz->nodo->de=NULL;
         delete iz;
         iz=NULL;
         borrado=true;
      }
      else if ( nVolumen == pVolumen && iz == NULL)
      {
         this->nodo->item=de->nodo->item;
         this->nodo->de=de->nodo->de;
         this->nodo->iz=de->nodo->iz;
         de->nodo->iz=de->nodo->de=NULL;
         delete de;
         de=NULL;
         borrado=true;
      }
      else if ( nVolumen==pVolumen && iz != NULL && de != NULL)
      {/*
         while(iz->nodo->de !=NULL)
         {
            de=iz;
            iz=iz->nodo->de;
         }
         this->nodo->item=iz->nodo->item;
         if(iz!=this->nodo->iz)de->nodo->de=NULL;
         else this->nodo->iz=this->nodo->iz->nodo->iz;
         delete iz;
         borrado=true;*/
          while(iz->nodo->de !=NULL)
         {
            de=iz;
            iz=iz->nodo->de;
         }
         this->nodo->item=iz->nodo->item;
         if(de==this->nodo->de)this->nodo->iz=iz->nodo->iz;
         else de->nodo->de=iz->nodo->iz;
         iz->nodo->iz=NULL;
         delete iz;
         borrado=true;
      }
      return borrado;
   }
}
// Devuelve TRUE si el elemento está en el árbol, FALSE en caso contrario
bool TABBPoro::Buscar(const TPoro &poro)const
{
   if(this == NULL || this->nodo==NULL)
      return false;
   else
      if(this->nodo->item.Volumen()==poro.Volumen())
         return true;
      else
         if(this->nodo->item.Volumen()>poro.Volumen ())
            return this->nodo->iz->Buscar(poro);
         else
            return this->nodo->de->Buscar(poro);
}
// Devuelve el elemento en la raíz del árbol
TPoro TABBPoro::Raiz()const
{
   TPoro nuevo;
   if(nodo != NULL)
      return this->nodo->item;
   else
      return nuevo;
}
// Devuelve la altura del árbol (la altura de un árbol vacío es 0)
int TABBPoro::Altura()const
{
   int altura=0;
   if(this!=NULL && this->nodo!=NULL)
   {
      altura++;
      int alturaIZ=this->nodo->iz->Altura();
      int alturaDE=this->nodo->de->Altura();
      if(alturaIZ < alturaDE)
         altura+=alturaDE;
      else
         altura+=alturaIZ;
   }
   return altura;
}
// Devuelve el número de nodos del árbol (un árbol vacío posee 0 nodos)
int TABBPoro::Nodos()const
{
   int nodos=0;
   if(this != NULL && this->nodo!=NULL)
   {
      nodos++;
      int nodosIZ=this->nodo->iz->Nodos();
      int nodosDE=this->nodo->de->Nodos();
      nodos+=nodosIZ+nodosDE;
   }
   return nodos;
}
// Devuelve el número de nodos hoja en el árbol (la raíz puede ser nodo hoja)
int TABBPoro::NodosHoja()const
{
   int nodos=0;
   if(this != NULL && this->nodo!=NULL)
   {
      if(this->nodo->iz==NULL && this->nodo->de==NULL) nodos++;
      int nodosIZ=this->nodo->iz->NodosHoja();
      int nodosDE=this->nodo->de->NodosHoja();
      nodos+=nodosIZ+nodosDE;
   }
   return nodos;
}
// Suma de dos ABB
TABBPoro TABBPoro::operator+(const TABBPoro &otro)
{
   TABBPoro nuevo(*this);
   TABBPoro nuevo2(otro);
   TVectorPoro vector=nuevo2.Niveles();
   int longitud = vector.Longitud();
   for(int i=1; i<=longitud; i++)nuevo.Insertar(vector[i]);
   return nuevo;
}
// Resta de dos ABB
TABBPoro TABBPoro::operator-(const TABBPoro &otro)
{
   TABBPoro nuevo;
   TVectorPoro vector=this->Niveles();
   int longitud=vector.Longitud();
   for(int i=1; i<=longitud; i++)
   {
      if(!otro.Buscar(vector[i]))
      {
         nuevo.Insertar(vector[i]);
      }
   }
   return nuevo;
}
// Devuelve el recorrido en inorden
TVectorPoro TABBPoro::Inorden()const
{
   TVectorPoro vector;
   TVectorPoro vector1;
   TVectorPoro vector2;
   if(this->nodo!=NULL)
   {
      if(this->nodo->iz!=NULL)
      {
         vector1=this->nodo->iz->Inorden();
         vector.Redimensionar(vector.Longitud()+vector1.Longitud());
         for(int j=1,i=vector.Cantidad()+1; i<=vector.Longitud(); i++, j++)
         {
            vector[i]=vector1[j];
         }
      }
      if(!this->nodo->item.EsVacio())
      {
         vector.Redimensionar(vector.Longitud()+1);
         vector[vector.Longitud()]=nodo->item;
      }
      if(this->nodo->de!=NULL)
      {
         vector2=this->nodo->de->Inorden();
         vector.Redimensionar(vector.Longitud()+vector2.Longitud());
         for(int j=1,i=vector.Cantidad()+1; i<=vector.Longitud(); i++, j++)
         {
            vector[i]=vector2[j];
         }
      }   }
   return vector;
}
// Devuelve el recorrido en preorden
TVectorPoro TABBPoro::Preorden()const
{
   TVectorPoro vector;
   TVectorPoro vector1;
   TVectorPoro vector2;
   if(this->nodo!=NULL)
   {
      if(!this->nodo->item.EsVacio())
      {
         vector.Redimensionar(1);
         vector[1]=nodo->item;
      }
      if(this->nodo->iz!=NULL)
      {
         vector1=this->nodo->iz->Preorden();
         vector.Redimensionar(1+vector1.Longitud());
         for(int j=1,i=2; i<=vector.Longitud(); i++, j++)
         {
            vector[i]=vector1[j];
         }
      }
      if(this->nodo->de!=NULL)
      {
         vector2=this->nodo->de->Preorden();
         vector.Redimensionar(vector.Longitud()+vector2.Longitud());
         for(int j=1,i=vector.Cantidad()+1; i<=vector.Longitud(); i++, j++)
         {
            vector[i]=vector2[j];
         }
      }
   }
   return vector;
}
// Devuelve el recorrido en postorden
TVectorPoro TABBPoro::Postorden()const
{
   TVectorPoro vector;
   TVectorPoro vector1;
   TVectorPoro vector2;
   if(this->nodo!=NULL)
   {
      if(this->nodo->iz!=NULL)
      {
         vector1=this->nodo->iz->Postorden();
         vector.Redimensionar(vector.Longitud()+vector1.Longitud());
         for(int j=1,i=vector.Cantidad()+1; i<=vector.Longitud(); i++, j++)
         {
            vector[i]=vector1[j];
         }
      }
      if(this->nodo->de!=NULL)
      {
         vector2=this->nodo->de->Postorden();
         vector.Redimensionar(vector.Longitud()+vector2.Longitud());
         for(int j=1,i=vector.Cantidad()+1; i<=vector.Longitud(); i++, j++)
         {
            vector[i]=vector2[j];
         }
      }
      if(!this->nodo->item.EsVacio())
      {
         vector.Redimensionar(vector.Longitud()+1);
         vector[vector.Longitud()]=nodo->item;
      }
   }
   return vector;
}
// AUXILIAR : Devuelve el recorrido en inorden
void TABBPoro::InordenAux(TVectorPoro &, int &)
{

}
// AUXILIAR : Devuelve el recorrido en preorden
void TABBPoro::PreordenAux(TVectorPoro &, int &)
{

}
// AUXILIAR : Devuelve el recorrido en postorden
void TABBPoro::PostordenAux(TVectorPoro &, int &)
{

}
// Devuelve el recorrido por niveles
TVectorPoro TABBPoro::Niveles()
{
   TVectorPoro vector;
   int longVector=vector.Longitud();
   TColaABBPoro cola;
   TABBPoro* nuevo;
   if(this->nodo!=NULL)cola.Encolar(this);
   while(!cola.EsVacia())
   {
      nuevo=cola.Cabeza();
      longVector++;
      vector.Redimensionar(longVector);
      vector[longVector]=nuevo->nodo->item;
      if(nuevo->nodo->iz!=NULL)cola.Encolar(nuevo->nodo->iz);
      if(nuevo->nodo->de!=NULL)cola.Encolar(nuevo->nodo->de);
      cola.Desencolar();
   }
   return vector;
}

// Sobrecarga del operador salida
ostream& operator<<(ostream &os,const TABBPoro &Arbol)
{
   TABBPoro nuevo(Arbol);
   os << nuevo.Niveles();
   return os;
}


